{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Compress String LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: compressString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串<code>aabcccccaaa</code>会变为<code>a2b1c5a3</code>。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。</p>\n",
    "\n",
    "<p> <strong>示例1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>：\"aabcccccaaa\"\n",
    "<strong> 输出</strong>：\"a2b1c5a3\"\n",
    "</pre>\n",
    "\n",
    "<p> <strong>示例2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong> 输入</strong>：\"abbccd\"\n",
    "<strong> 输出</strong>：\"abbccd\"\n",
    "<strong> 解释</strong>：\"abbccd\"压缩后为\"a1b2c2d1\"，比原字符串长度更长。\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "<li>字符串长度在[0, 50000]范围内。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [compress-string-lcci](https://leetcode.cn/problems/compress-string-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [compress-string-lcci](https://leetcode.cn/problems/compress-string-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        #s = \"\".join([\"%s%d\" % (a, len(list(b))) for a, b in groupby(S)])\n",
    "        s = \"\"\n",
    "        for a, b in groupby(S):\n",
    "           s += \"\".join(\"%s%d\" % (a, sum(1 for _ in b)))\n",
    "           #len(list(b))\n",
    "        if len(s)<len(S):\n",
    "            return s\n",
    "        return S\n",
    "\n",
    " \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if not S: return ''\n",
    "        pre_s = S[0]\n",
    "        pre_le = 1\n",
    "        S+='/'\n",
    "        ans = ''\n",
    "        for i in S[1:]:\n",
    "            if i==pre_s:\n",
    "                pre_le+=1\n",
    "            else:\n",
    "                ans+=pre_s\n",
    "                ans+=str(pre_le)\n",
    "                pre_s = i\n",
    "                pre_le = 1\n",
    "        if len(ans)>=(len(S)-1):\n",
    "            return S[:-1]\n",
    "        else:\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        out = \"\"\n",
    "        now = \"\"\n",
    "        num = 0\n",
    "        for i in range(len(S)):\n",
    "            if i==0:\n",
    "                now = S[i]\n",
    "            if now==S[i] :\n",
    "                num+=1\n",
    "            else:\n",
    "                out+=now\n",
    "                out+=str(num)\n",
    "                now = S[i]\n",
    "                num = 1\n",
    "            if i==len(S)-1:\n",
    "                out+=now\n",
    "                out+=str(num)\n",
    "        if len(out)>=len(S):return S\n",
    "        else:return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if len(S) == 0: return S\n",
    "        ans = \"\"\n",
    "        cur = S[0]\n",
    "        cnt = 0\n",
    "        for c in S:\n",
    "            if c == cur:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ans += cur + str(cnt)\n",
    "                cnt = 1\n",
    "                cur = c\n",
    "        ans += cur + str(cnt)\n",
    "        return ans if len(ans) < len(S) else S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        left,right = 0,0\n",
    "        ans = \"\"\n",
    "        while left <len(S):\n",
    "            ch = S[left]\n",
    "            while  right<len(S) and ch == S[right]:\n",
    "                right += 1\n",
    "            ans += str(ch) + str(right-left)\n",
    "            left = right\n",
    "        return ans if len(ans) < len(S) else S\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        # if len(S) <= 1:\n",
    "        #     return S\n",
    "        \n",
    "        # i,j = 0, 0\n",
    "        # n = len(S)\n",
    "        # res = []\n",
    "        # while i < n:\n",
    "        #     while j < n and S[j] == S[i]:\n",
    "        #         j += 1\n",
    "        #     res.append(S[i])\n",
    "        #     res.append(str(j - i))\n",
    "        #     i = j\n",
    "        # res = \"\".join(res)\n",
    "        # if len(res) >= n:\n",
    "        #     return S\n",
    "        # else:\n",
    "        #     return res\n",
    "\n",
    "        if len(S) <= 1:\n",
    "            return S\n",
    "        \n",
    "        i, j = 0, 1\n",
    "        n = len(S)\n",
    "        res = \"\"\n",
    "        while j < n:\n",
    "            if S[j] == S[i]:\n",
    "                val = S[j]\n",
    "                while j < n and S[j] == val:\n",
    "                    j += 1\n",
    "                res += S[i] + str(j-i)\n",
    "            else:\n",
    "                res += S[i] + str(j-i)\n",
    "            i = j\n",
    "        return res if len(res) < len(S) else S\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        # if len(S) <= 1:\n",
    "        #     return S\n",
    "        \n",
    "        # i,j = 0, 0\n",
    "        # n = len(S)\n",
    "        # res = []\n",
    "        # while i < n:\n",
    "        #     while j < n and S[j] == S[i]:\n",
    "        #         j += 1\n",
    "        #     res.append(S[i])\n",
    "        #     res.append(str(j - i))\n",
    "        #     i = j\n",
    "        # res = \"\".join(res)\n",
    "        # if len(res) >= n:\n",
    "        #     return S\n",
    "        # else:\n",
    "        #     return res\n",
    "\n",
    "        if len(S) <= 1:\n",
    "            return S\n",
    "        \n",
    "        i, j = 0, 1\n",
    "        n = len(S)\n",
    "        res = \"\"\n",
    "        while j < n:\n",
    "            if S[j] == S[i]:\n",
    "                val = S[j]\n",
    "                while j < n and S[j] == val:\n",
    "                    j += 1\n",
    "                res += S[i] + str(j-i)\n",
    "            else:\n",
    "                res += S[i] + str(j-i)\n",
    "                # j += 1\n",
    "            i = j\n",
    "        return res if len(res) < len(S) else S\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        ans=''\n",
    "        n=len(S)\n",
    "        if n>0:\n",
    "            cnt,c=1,S[0]\n",
    "            ans=ans+c\n",
    "            for index in range(1,n):\n",
    "                if S[index] !=c:\n",
    "                    ans=ans+str(cnt)+S[index]\n",
    "                    cnt=1\n",
    "                    c=S[index]\n",
    "                else:\n",
    "                    cnt+=1\n",
    "            ans=ans+str(cnt)\n",
    "        return ans if len(ans)<n else S\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        res = ''\n",
    "        l = r = 0\n",
    "        S += '*'\n",
    "        n = len(S)\n",
    "        while r < n:\n",
    "            if S[l] == S[r]:\n",
    "                r += 1\n",
    "            else:\n",
    "                res += f\"{S[l]}{r-l}\"\n",
    "                l = r \n",
    "        return res if len(res) < n-1 else S[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        res = ''\n",
    "        n = len(S)\n",
    "        if n == 0:\n",
    "            return S\n",
    "        res += S[0]\n",
    "        tmp = 1\n",
    "        for i in range(1, n):\n",
    "            if S[i] != S[i-1]:\n",
    "                res += str(tmp)\n",
    "                res += S[i]\n",
    "                tmp = 1\n",
    "            else:\n",
    "                tmp += 1\n",
    "        if n > len(res+str(tmp)):\n",
    "            return res+str(tmp)\n",
    "        else:\n",
    "            return S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if not S: return S\n",
    "        l = 0\n",
    "        res = \"\"\n",
    "        n = len(S)\n",
    "        for r in range(n):\n",
    "            if S[r] != S[l]:\n",
    "                res += S[l]+str(r-l)\n",
    "                l = r \n",
    "        # if r==n:\n",
    "        res += S[l]+str(n-l)\n",
    "        if len(res)>=n:\n",
    "            return S\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if len(S) == 0 or len(S) == 1:\n",
    "            return S\n",
    "        ans = ''\n",
    "        count = 1\n",
    "        for i in range(1, len(S)):\n",
    "            if S[i] != S[i-1]:\n",
    "                ans += S[i-1]\n",
    "                ans += str(count)\n",
    "                count = 1\n",
    "            else:\n",
    "                count += 1\n",
    "        ans += S[len(S)-1]\n",
    "        ans += str(count) \n",
    "        return ans if len(S) > len(ans) else S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if len(S)<=2: return S\n",
    "\n",
    "        s = \"\"\n",
    "        lp=rp=0\n",
    "\n",
    "        for i in range(len(S)):\n",
    "            if S[lp]!=S[rp]:\n",
    "                s+=S[lp]\n",
    "                s+= str(rp-lp)\n",
    "                lp=rp\n",
    "            rp+=1\n",
    "\n",
    "        s+=S[lp]\n",
    "        s+= str(rp-lp)\n",
    "\n",
    "        return s if len(s)<len(S) else S\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        res = ''\n",
    "        s = S\n",
    "        n = len(s)\n",
    "        left = 0\n",
    "        s += '?'\n",
    "        for i in range(n+1):\n",
    "            if s[left] != s[i]:\n",
    "                res += s[left] + str(i-left)\n",
    "                left = i\n",
    "        \n",
    "        return res if len(res) < n else S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        slow, fast = 0, 0\n",
    "        L = len(S)\n",
    "        res = \"\"\n",
    "\n",
    "        while fast < L:\n",
    "            while fast < L and S[fast] == S[slow]:\n",
    "                fast += 1\n",
    "\n",
    "            res += S[slow]\n",
    "            res += str(fast-slow)\n",
    "\n",
    "            slow = fast\n",
    "\n",
    "        if len(S)<= len(res):\n",
    "            return S\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        l = len(S)\n",
    "        S += '*'\n",
    "        i = 0\n",
    "        j = 1\n",
    "        k = \"\"\n",
    "        while j <= l:\n",
    "            if S[j] == S[i] :\n",
    "                j += 1\n",
    "            else:\n",
    "                k += str(S[i])+str(j - i)\n",
    "                i = j\n",
    "                j += 1\n",
    "        if len(k) >= l:\n",
    "            return S[:-1]\n",
    "        else:\n",
    "            return k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if len(S) < 2:\n",
    "            return S\n",
    "        count = 1\n",
    "        res = ''\n",
    "        for i in range(1, len(S)):\n",
    "            if S[i] == S[i-1]:\n",
    "                count += 1\n",
    "            else:\n",
    "                res += S[i-1] + str(count)\n",
    "                count = 1\n",
    "        res += S[i] + str(count)\n",
    "        if len(res) < len(S):\n",
    "            return res\n",
    "        else:\n",
    "            return S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if not S:\n",
    "            return \"\"\n",
    "        ch = S[0]\n",
    "        ans = ''\n",
    "        cnt = 0\n",
    "        for c in S:\n",
    "            if c == ch:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                ans += ch + str(cnt)\n",
    "                ch = c\n",
    "                cnt = 1\n",
    "        ans += ch + str(cnt)\n",
    "        return ans if len(ans) < len(S) else S\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if len(S) == 0:\n",
    "            return S\n",
    "        S = list(S)\n",
    "        lst = ''\n",
    "        ptr = 0\n",
    "        res = ''\n",
    "        ctr = None\n",
    "        while ptr < len(S):\n",
    "            if S[ptr] != lst:\n",
    "                if ctr:\n",
    "                    res += str(ctr)\n",
    "                    # print(res)\n",
    "                ctr = 1\n",
    "                res += S[ptr]\n",
    "            else:\n",
    "                ctr += 1\n",
    "            lst = S[ptr]\n",
    "            ptr += 1\n",
    "\n",
    "        if ctr:\n",
    "            res += str(ctr)\n",
    "\n",
    "        if len(res) >= len(S):\n",
    "            return ''.join(S)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        cnt = 1\n",
    "        res = ''\n",
    "        l, r = 0, 1\n",
    "        if len(S) in (0, 1):\n",
    "            return S\n",
    "        while r < len(S):\n",
    "            if S[l] == S[r]:\n",
    "                cnt += 1\n",
    "                if r == len(S) - 1:\n",
    "                    res = res + S[l] + str(cnt)\n",
    "                \n",
    "            elif S[l] != S[r]:\n",
    "                res = res + S[l] + str(cnt)\n",
    "                l = r\n",
    "                cnt = 1\n",
    "            r += 1\n",
    "        if l == len(S) - 1:\n",
    "            res = res + S[l] + str(cnt)\n",
    "        if len(res) >= len(S):\n",
    "            return S\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        now = \"\"\n",
    "        count = 0\n",
    "        result = []\n",
    "        for i in S:\n",
    "            if not now:\n",
    "                now = i\n",
    "                result.append(now)\n",
    "            if i == now:\n",
    "                count += 1\n",
    "            elif i != now:\n",
    "                result.append(count)\n",
    "                now = i\n",
    "                result.append(now)\n",
    "                count = 1\n",
    "        if count != 0:\n",
    "            result.append(count)\n",
    "        if len(result) < len(S):\n",
    "            return \"\".join(str(i) for i in result)\n",
    "        else:\n",
    "            return S\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        stack = []\n",
    "        for c in S:\n",
    "            if len(stack) == 0:\n",
    "                stack.append(c)\n",
    "                stack.append(1)\n",
    "            elif c == stack[-2]:\n",
    "                count = stack.pop()\n",
    "                stack.append(count + 1)\n",
    "            else:\n",
    "                stack.append(c)\n",
    "                stack.append(1)\n",
    "        \n",
    "        if len(stack) >= len(S):\n",
    "            return S\n",
    "\n",
    "        new_s = ''\n",
    "        for c in stack:\n",
    "            new_s += f\"{c}\"\n",
    "        return new_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if S == \"\":\n",
    "            return \"\"\n",
    "        if len(S) == 1:\n",
    "            return S\n",
    "        ans = \"\"\n",
    "        pos = 1\n",
    "        li = list(S)\n",
    "        for i in range(1,len(li)):\n",
    "            if li[i] == li[i-1]:\n",
    "                pos += 1\n",
    "            else:\n",
    "                ans = ans + str(li[i-1])\n",
    "                ans = ans + str(pos)\n",
    "                pos = 1\n",
    "        ans = ans + str(li[i])\n",
    "        ans = ans + str(pos)\n",
    "        if len(ans) >= len(S):\n",
    "            return S\n",
    "        else:\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# leetcode submit region begin(Prohibit modification and deletion)\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if len(S) == 0:\n",
    "            return S\n",
    "        S = list(S)\n",
    "        lst = ''\n",
    "        ptr = 0\n",
    "        res = ''\n",
    "        ctr = None\n",
    "        while ptr < len(S):\n",
    "            if S[ptr] != lst:\n",
    "                if ctr:\n",
    "                    res += str(ctr)\n",
    "                    # print(res)\n",
    "                ctr = 1\n",
    "                res += S[ptr]\n",
    "            else:\n",
    "                ctr += 1\n",
    "            lst = S[ptr]\n",
    "            ptr += 1\n",
    "\n",
    "        if ctr:\n",
    "            res += str(ctr)\n",
    "\n",
    "        if len(res) >= len(S):\n",
    "            return ''.join(S)\n",
    "        return res\n",
    "\n",
    "# leetcode submit region end(Prohibit modification and deletion)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        S_old = S\n",
    "        n = len(S)\n",
    "        if n == 0:\n",
    "            return S\n",
    "\n",
    "        S = list(S)\n",
    "        tmp = S[0]\n",
    "        count = 1\n",
    "\n",
    "        S1 = ''\n",
    "        for i in range(1, n):\n",
    "            if tmp == S[i]:\n",
    "                count += 1\n",
    "            else:\n",
    "                S1 = S1 + tmp + str(count)\n",
    "                tmp = S[i]\n",
    "                count = 1\n",
    "\n",
    "        S1 = S1 + tmp + str(count)\n",
    "        return S1 if len(S1) < len(S) else S_old\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        now = \"\"\n",
    "        count = 0\n",
    "        result = []\n",
    "        for i in S:\n",
    "            if not now:\n",
    "                now = i\n",
    "                result.append(now)\n",
    "            if i == now:\n",
    "                count += 1\n",
    "            elif i != now:\n",
    "                result.append(count)\n",
    "                now = i\n",
    "                result.append(now)\n",
    "                count = 1\n",
    "        result.append(count)\n",
    "        if len(result) < len(S):\n",
    "            return \"\".join(str(i) for i in result)\n",
    "        else:\n",
    "            return S\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        i, j  = 0, 0\n",
    "        res = []\n",
    "        while i < len(S):\n",
    "            if S[j] == S[i]:\n",
    "                j += 1\n",
    "                if j > len(S) - 1:\n",
    "                    res.append(S[i])\n",
    "                    res.append(j-i)\n",
    "                    break\n",
    "            else:\n",
    "                res.append(S[i])\n",
    "                res.append(j-i)\n",
    "                i = j\n",
    "                j += 1\n",
    "                if j > len(S) - 1:\n",
    "                    res.append(S[i])\n",
    "                    res.append(j-i)\n",
    "                    break\n",
    "        s = ''\n",
    "        for item in res:\n",
    "            s += str(item)\n",
    "        if len(s) >= len(S):\n",
    "            return S\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if S != '':\n",
    "            temp = S[0]\n",
    "            num = 0\n",
    "            lst = [temp]\n",
    "            res = ''\n",
    "            for letter in S:\n",
    "                if letter == '\"':\n",
    "                    continue\n",
    "                elif letter == temp:\n",
    "                    num += 1\n",
    "                else:\n",
    "                    temp = letter\n",
    "                    lst.append(num)\n",
    "                    lst.append(temp)\n",
    "                    num = 1\n",
    "            lst.append(num)\n",
    "            for i in range(len(lst)):\n",
    "                res += str(lst[i])\n",
    "            if len(res) < len(S):\n",
    "                return res\n",
    "            else:\n",
    "                return S\n",
    "        return S\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        str1=list(S)\n",
    "        ans=''\n",
    "        l=len(str1)\n",
    "        a=[]\n",
    "        fi=''\n",
    "        if l==1:\n",
    "            return S\n",
    "        if l==2:\n",
    "            return S\n",
    "        if l==3:\n",
    "            return str1[0]+'3'\n",
    "        else:\n",
    "            for i in range(l-1):\n",
    "                if str1[i+1]!=str1[i]:\n",
    "                    a.append(i)\n",
    "            for i in range(1,len(a)):\n",
    "                f1=str1[a[0]]+str(a[0]+1)\n",
    "                fl=str1[a[len(a)-1]+1]+str(l-a[-1]-1)\n",
    "                fi=fi+str1[a[i]]+str(a[i]-a[i-1])\n",
    "                ans=f1+fi+fl\n",
    "            if len(ans)>=len(S):\n",
    "                return S \n",
    "            else:\n",
    "                return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        s = list(S)\n",
    "        count = 0\n",
    "        idx = 0\n",
    "        char = None\n",
    "        rst = \"\"\n",
    "        while idx < len(s):\n",
    "            if char == s[idx]:\n",
    "                count += 1\n",
    "            else:\n",
    "                if char:\n",
    "                    rst += (char + str(count))\n",
    "                char = s[idx]\n",
    "                count = 1\n",
    "            idx += 1\n",
    "        \n",
    "        rst += (char + str(count)) if count > 0 else \"\"\n",
    "        return rst if len(rst) < len(s) else S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "\n",
    "        l1 = []\n",
    "        l2 = []\n",
    "\n",
    "        h = 0\n",
    "\n",
    "        while h < len(S):\n",
    "            s = S[h]\n",
    "            l1.append(s)\n",
    "            l2.append(1)\n",
    "            h += 1\n",
    "            while h < len(S) and S[h] == s:\n",
    "\n",
    "                h+=1\n",
    "                l2[-1] += 1\n",
    "            \n",
    "        text = \"\"\n",
    "        for i1, i2 in zip(l1, l2):\n",
    "            text += str(i1) + str(i2)\n",
    "        \n",
    "        if len(text) >= len(S):\n",
    "            return S\n",
    "        else:\n",
    "            return text"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if not S:\n",
    "            return S\n",
    "        n = len(S)\n",
    "        left = 0\n",
    "        right = 0\n",
    "        while right < len(S)-1:\n",
    "            right += 1\n",
    "            if S[left] == S[right]:\n",
    "                continue\n",
    "            else:\n",
    "                S = S[:left] + S[left] + str(right-left) + S[right:]\n",
    "                left += len(str(right-left)) + 1\n",
    "                right = left\n",
    "        S = S[:left] + S[left] + str(right-left+1)\n",
    "        print(S)\n",
    "        if len(S) < n:\n",
    "            return S   \n",
    "        i = 1\n",
    "        j = 0\n",
    "        alpha = S[0]\n",
    "        tim = 0\n",
    "        while i < len(S):\n",
    "            j = i\n",
    "            while i < len(S) and S[i].isdigit():\n",
    "                tim = tim*10 + int(S[i])\n",
    "                i += 1\n",
    "            temp = ''\n",
    "            for k in range(tim):\n",
    "                temp = temp + alpha\n",
    "            S = S[:j-1] + temp + S[i:]\n",
    "            i += tim - 1\n",
    "            if i < len(S):\n",
    "                alpha = S[i-1]\n",
    "                tim = 0\n",
    "            else:\n",
    "                break\n",
    "        return S\n",
    "\n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        stack, nums = [], []\n",
    "        for i in range(len(S)):\n",
    "            if not stack or S[i] != stack[-1]:\n",
    "                stack.append(S[i])\n",
    "                nums.append(1)\n",
    "                continue\n",
    "            else:\n",
    "                nums[-1] += 1\n",
    "        res = ''\n",
    "        for i in range(len(stack)):\n",
    "            res += stack[i] + str(nums[i])\n",
    "        return res if len(S) > len(res) else S\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        i, j, ls = 0, 0, len(S)\n",
    "        res = []\n",
    "        while i < ls:\n",
    "            while j < ls and S[i] == S[j]:\n",
    "                j += 1\n",
    "            res.append(S[i])\n",
    "            res.append(str(j - i))\n",
    "            i = j\n",
    "        res = ''.join(res)\n",
    "        return res if len(res) < ls else S\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        temp = []\n",
    "        i, n = 0, len(S)\n",
    "\n",
    "        while i < n:\n",
    "            j = i + 1\n",
    "            while j < n and S[j] == S[i]:\n",
    "                j += 1\n",
    "            temp.append(f'{S[i]}{j - i}')\n",
    "            i = j\n",
    "\n",
    "        compressed = ''.join(temp)\n",
    "        return compressed if len(compressed) < n else S\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if not S:\n",
    "            return S\n",
    "        n = len(S)\n",
    "        left = 0\n",
    "        right = 0\n",
    "        while right < len(S)-1:\n",
    "            right += 1\n",
    "            if S[left] == S[right]:\n",
    "                continue\n",
    "            else:\n",
    "                S = S[:left] + S[left] + str(right-left) + S[right:]\n",
    "                left += len(str(right-left)) + 1\n",
    "                right = left\n",
    "        S = S[:left] + S[left] + str(right-left+1)\n",
    "        print(S)\n",
    "        if len(S) < n:\n",
    "            return S   \n",
    "        i = 1\n",
    "        j = 0\n",
    "        alpha = S[0]\n",
    "        tim = 0\n",
    "        while i < len(S):\n",
    "            j = i\n",
    "            while i < len(S) and S[i].isdigit():\n",
    "                tim = tim*10 + int(S[i])\n",
    "                i += 1\n",
    "            temp = ''\n",
    "            for k in range(tim):\n",
    "                temp = temp + alpha\n",
    "            S = S[:j-1] + temp + S[i:]\n",
    "            i += tim - 1\n",
    "            if i < len(S):\n",
    "                alpha = S[i-1]\n",
    "                tim = 0\n",
    "            else:\n",
    "                break\n",
    "        return S\n",
    "\n",
    "         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        i = 0\n",
    "        res = []\n",
    "        j = 0\n",
    "        while(i < len(S) and j < len(S)):\n",
    "            res.append(S[i])\n",
    "            count = 0\n",
    "            while (j < len(S)):\n",
    "                if S[j] == S[i]:\n",
    "                    count += 1\n",
    "                    #print(\"S[{}] = {}, S[{}] = {}\".format(i, S[i], j, S[j]))\n",
    "                    #print(\"count\", count)\n",
    "                    j += 1\n",
    "                else: # not equal\n",
    "                    #print(\"else i = {}, j = {}\".format(i, j))\n",
    "                    i = j\n",
    "                    break\n",
    "            res.append(str(count))\n",
    "\n",
    "        if len(S) <= len(res):\n",
    "            return S\n",
    "        else:\n",
    "            return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if not S: return \"\"\n",
    "        S = list(S)\n",
    "        count = 0\n",
    "        ch = S[0]\n",
    "        res = list()\n",
    "        for i,s in enumerate(S):\n",
    "            if s == ch:\n",
    "                count +=1\n",
    " \n",
    "            else:\n",
    "                res += S[i-1]+f'{count}'\n",
    "                ch = s\n",
    "                count = 1\n",
    "\n",
    "        res += s +f'{count}'\n",
    "        res = ''.join(res)\n",
    "        if len(res) >= len(S) : return  ''.join(S)\n",
    "        return res\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        res = []\n",
    "        i,j,l = 0,0,len(S)\n",
    "        while i<l:\n",
    "            count=0\n",
    "            while j<l and S[j] == S[i]:\n",
    "                count+=1\n",
    "                j+=1\n",
    "            res.extend([S[i],str(count)])\n",
    "            i=j\n",
    "        \n",
    "        return min(S,\"\".join(res),key=len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if S=='':\n",
    "            return ''\n",
    "        chars=list(S)\n",
    "        i=1\n",
    "        cal=0\n",
    "        q=1\n",
    "        p=0\n",
    "        n=0\n",
    "        t=chars[0]\n",
    "        while i<len(chars):\n",
    "            # print(chars,i,q)\n",
    "            if chars[i]!=t:\n",
    "                t=chars[i]\n",
    "                if q==1:\n",
    "                    p=i\n",
    "                    n+=1\n",
    "                else:\n",
    "                    e=str(q)\n",
    "                    j=p+1\n",
    "                    lon=len(e)\n",
    "                    k=0\n",
    "                    while j<i:\n",
    "                        if k<lon:\n",
    "                            chars[j]=e[k]\n",
    "                            k+=1\n",
    "                        else:\n",
    "                            chars[j]=''\n",
    "                        j+=1\n",
    "                \n",
    "                    p=i\n",
    "                q=1\n",
    "            else:\n",
    "                q+=1\n",
    "            i+=1\n",
    "        print(q) \n",
    "        print(n,888)       \n",
    "        if q==1:\n",
    "            p=i\n",
    "            n+=1\n",
    "            i+=1\n",
    "        else:\n",
    "            e=str(q)\n",
    "            j=p+1\n",
    "            lon=len(e)\n",
    "            k=0\n",
    "            while j<i:\n",
    "                if k<lon:\n",
    "                    chars[j]=e[k]\n",
    "                    k+=1\n",
    "                else:\n",
    "                    chars[j]=''\n",
    "                j+=1\n",
    "            while k<lon:\n",
    "                chars.append(e[k])\n",
    "                k+=1\n",
    "        if '' in chars:\n",
    "            r=chars.index('')\n",
    "            i=r\n",
    "            j=r\n",
    "            while i<len(chars):\n",
    "                if chars[i]!='':\n",
    "                    chars[j]=chars[i]\n",
    "                    j+=1\n",
    "                i+=1\n",
    "                \n",
    "            chars=chars[:j]\n",
    "            print(r)\n",
    "        print(chars,999,len(chars),n,len(S))\n",
    "        if len(chars)+n>=len(S):\n",
    "            return S\n",
    "        lo=len(chars)\n",
    "        ans=[]\n",
    "        print(lo)\n",
    "        for i in range(lo):\n",
    "            ans.append(chars[i])\n",
    "            if (i==lo-1 and chars[i]>='A') or (chars[i]>='A' and chars[i+1]>='A'):\n",
    "                ans.append('1')\n",
    "        #         print(9,chars[i+1])\n",
    "        #     print(i,chars[i],ans)\n",
    "        # print(chars)    \n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S):\n",
    "        if not S:\n",
    "            return \"\"\n",
    "        res = []\n",
    "        i = 0\n",
    "        j = 0\n",
    "        n = len(S)\n",
    "        while i < n:\n",
    "            while j < n and S[i] == S[j]:\n",
    "                j += 1\n",
    "            res.append(S[i])\n",
    "            res.append(str(j-i))\n",
    "            i = j\n",
    "        res =  ''.join(res)\n",
    "        return res if len(res) < n else S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if S == \"\":\n",
    "            return S\n",
    "        S1 = []\n",
    "        S1.append(S[0])\n",
    "        S1.append(1)\n",
    "        k = 0\n",
    "        for i in range(1,len(S)):\n",
    "            if S[i] == S1[k]:\n",
    "                S1[k+1] += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                S1.append(S[i])\n",
    "                S1.append(1)\n",
    "                k += 2\n",
    "        S1 = ''.join('%s'%id for id in(S1))\n",
    "        if len(S) > len(S1):\n",
    "            return S1\n",
    "        return S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#双指针\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        res=[]\n",
    "        i,j=0,0\n",
    "        while i < len(S):\n",
    "            while j < len(S) and S[j]==S[i]:\n",
    "                j+=1\n",
    "            res.append(S[i])\n",
    "            res.append(str(j-i))\n",
    "            i=j\n",
    "        res=''.join(res)\n",
    "        if len(res)>=len(S):\n",
    "            return S\n",
    "        else:\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        res = []\n",
    "        i,l = 0,len(S)\n",
    "        while i<l:\n",
    "            count = 0\n",
    "            for j in range(i,l+1):\n",
    "                if j == l:\n",
    "                    res.extend([S[i],str(count)])\n",
    "                    i=j\n",
    "                    break\n",
    "                if S[j] == S[i]:\n",
    "                    count += 1\n",
    "                else:\n",
    "                    res.extend([S[i],str(count)])\n",
    "                    #res = res + S[i] + str(count)\n",
    "                    i=j\n",
    "                    break\n",
    "        return min(S,\"\".join(res),key=len)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if len(S)<=1:\n",
    "            return S\n",
    "        s=list()\n",
    "        s.append(S[0])\n",
    "        flag=1\n",
    "        for i in range(1,len(S)):\n",
    "            if S[i]==S[i-1]and i!=len(S)-1:\n",
    "                flag+=1\n",
    "            elif S[i]==S[i-1] and i==len(S)-1 :\n",
    "                flag+=1\n",
    "                s.append(str(flag))\n",
    "            else:\n",
    "                s.append(str(flag))\n",
    "                s.append(S[i])\n",
    "                flag=1\n",
    "                if i==len(S)-1:\n",
    "                    s.append(str(flag))\n",
    "        if len(s)>=len(S):\n",
    "            return S\n",
    "        else:\n",
    "            return ''.join(s)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "                \n",
    "\n",
    "       # S = \"aaaaaabbbbbcccddddd\" \n",
    "        len1 = len(S)\n",
    "        substringlist = []\n",
    "        i = 0\n",
    "        while i < (len(S)):\n",
    "            # current is i \n",
    "            end = i\n",
    "            while(1):\n",
    "                if end+1 == len1:\n",
    "                    substringlist.append(S[i:end+1])\n",
    "                    i = end+1\n",
    "                    break\n",
    "                if S[end] == S[end+1]:\n",
    "                    end = end + 1\n",
    "                    continue\n",
    "                if S[end] != S[end+1]:\n",
    "                    substringlist.append(S[i:end+1])\n",
    "                    i = end+1\n",
    "                    break\n",
    "\n",
    "#        print(substringlist)\n",
    "        output = \"\"\n",
    "        for i in range(len(substringlist)):\n",
    "            output= output + (substringlist[i][0])\n",
    "            output= output +  str((len(substringlist[i])))\n",
    "\n",
    "        len2 = len(output)\n",
    "        if len1<= len2:\n",
    "            return S\n",
    "    #   #      print(S)\n",
    "    #     if len1>len2:\n",
    "    #         print(output)\n",
    "        return output\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        start=0\n",
    "        n=len(S)\n",
    "        res=[]\n",
    "        for i in range(1,n+1):\n",
    "            if i==n:\n",
    "                res.append(S[start])\n",
    "                res.append(format(i-start))\n",
    "                break\n",
    "            if S[start]!=S[i]:\n",
    "                res.append(S[start])\n",
    "                res.append(format(i-start))\n",
    "                start=i\n",
    "        if len(res)>=len(S):\n",
    "            return S\n",
    "        \n",
    "        return \"\".join(res)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        tmp=[]\n",
    "        i=j=0\n",
    "        while j<len(S):\n",
    "            if S[j]!=S[j-1]:\n",
    "                ch=S[i:j]\n",
    "                tmp.append(ch)\n",
    "                i=j\n",
    "            j+=1\n",
    "        tmp.append(S[i:j])\n",
    "        res=''\n",
    "        for c in tmp:\n",
    "            if len(c)>0:\n",
    "                res+=str(c[0])+str(len(c))\n",
    "        if len(res)>=len(S):\n",
    "            return S\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        result = []\n",
    "        for s in S:\n",
    "            if result == [] or s != result[-2]:\n",
    "                result.append(s)\n",
    "                result.append(\"1\")\n",
    "            else:\n",
    "                result[-1] = str(int(result[-1])+1)\n",
    "        result = \"\".join(result)\n",
    "        return result if len(result) < len(S) else S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if not S:\n",
    "            return \"\"\n",
    "        ans = []\n",
    "        temp = 1\n",
    "        for i, val in enumerate(S[1:]):\n",
    "            if val == S[i]:\n",
    "                temp += 1\n",
    "            else:\n",
    "                ans.append(S[i]+str(temp))\n",
    "                temp = 1\n",
    "        ans.append(S[-1] + str(temp))\n",
    "        res = \"\".join(ans)\n",
    "        if len(res) >= len(S):\n",
    "            return S\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        compressed = []\n",
    "        stack = []\n",
    "        for s in S:\n",
    "            if stack and stack[-1] != s:\n",
    "                compressed.append(stack[-1])\n",
    "                compressed.append(str(len(stack)))\n",
    "                while stack:\n",
    "                    stack.pop()            \n",
    "            stack.append(s)\n",
    "        if stack:\n",
    "            compressed.append(stack[-1])\n",
    "            compressed.append(str(len(stack)))\n",
    "            compressed = ''.join(compressed)\n",
    "        return S if len(S) <= len(compressed) else compressed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        lst = []\n",
    "        for ch in S:\n",
    "            if lst == []:\n",
    "                lst.append(ch)\n",
    "                lst.append('1')\n",
    "            elif ch == lst[-2]:\n",
    "                lst.append(str(int(lst.pop())+1))\n",
    "            else:\n",
    "                lst.append(ch)\n",
    "                lst.append('1')\n",
    "        string = ''.join(lst)\n",
    "        return string if len(string) < len(S) else S\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        list1 = []\n",
    "        num = 1\n",
    "        if len(S) >1:\n",
    "            for i in range(1,len(S)):\n",
    "                if S[i-1] != S[i]:\n",
    "                    num = 1\n",
    "                    if i-1 == 0:\n",
    "                        list1.append(S[i-1])\n",
    "                        list1.append(num)\n",
    "                    else:\n",
    "                        list1.append(S[i])\n",
    "                        list1.append(num)\n",
    "                else:\n",
    "                    num += 1\n",
    "                    if S[i] not in list1:\n",
    "                        list1.append(S[i])\n",
    "                        list1.append(num)\n",
    "                    if S[i] in list1:\n",
    "                        list1[-1] = num\n",
    "            a = ''.join(map(str, list1))\n",
    "            if len(a) >= len(S):\n",
    "                return S\n",
    "            else:\n",
    "                return a\n",
    "        if len(S) <= 1:\n",
    "            return S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        n=len(S)\n",
    "        if n<=1:\n",
    "            return S\n",
    "        i,j=0,1\n",
    "        s=list(S)\n",
    "        ret=[]\n",
    "        while i<=n-1:\n",
    "            if j==n or s[i]!=s[j]:\n",
    "                ret.append(s[i])\n",
    "                ret.append(str(j-i))\n",
    "                i=j\n",
    "            j+=1\n",
    "        #print(ret)\n",
    "        if len(ret)>=n:\n",
    "            return S\n",
    "        else:\n",
    "            return \"\".join(ret)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if S:\n",
    "            lst = [[S[0], 0]]\n",
    "            for c in S:\n",
    "                if c == lst[-1][0]:\n",
    "                    lst[-1][1] += 1\n",
    "                else:\n",
    "                    lst.append([c, 1])\n",
    "            tmp = \"\"\n",
    "            for l in lst:\n",
    "                tmp += \"%s%d\" % (l[0], l[1])\n",
    "            str_rlt = S if len(tmp) >= len(S) else tmp\n",
    "        else:\n",
    "            str_rlt = \"\"\n",
    "        return str_rlt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if not S:\n",
    "            return ''\n",
    "        list1 = [S[0],'1']\n",
    "        for a in S[1:]:\n",
    "            if a == list1[-2]:\n",
    "                list1[-1] = str(int(list1[-1]) + 1)\n",
    "            else:\n",
    "                list1 += [a,\"1\"]\n",
    "        if len(S) <= len(list1):\n",
    "            return S\n",
    "        else:\n",
    "            return ''.join(list1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        s = S + ' '\n",
    "        res = []\n",
    "        result = ''\n",
    "        for a in s:\n",
    "            if  not res:\n",
    "                res.append([a,1])\n",
    "            else:\n",
    "                if a == res[-1][0]:\n",
    "                    res[-1][1] += 1\n",
    "                else:\n",
    "                    result += str(res[-1][0])+str(res[-1][1])\n",
    "                    res.append([a,1])\n",
    "                    \n",
    "       \n",
    "        \n",
    "        return result if len(result) < len(S) else S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        cnt = []\n",
    "        last = -1\n",
    "        for i in S:\n",
    "            if(last==-1 or i!=cnt[last][0]):\n",
    "                cnt.append([i, 1])\n",
    "                last +=1\n",
    "                continue\n",
    "            cnt[last][1]+=1\n",
    "        res = \"\"\n",
    "        for letter, amt in cnt:\n",
    "            res+=letter+str(amt)\n",
    "        return S if(len(res)>=len(S)) else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        w=[]\n",
    "        index=0\n",
    "        n=len(S)\n",
    "        while n>index :\n",
    "            size=len(w)\n",
    "            if size==0:\n",
    "                w.append(S[index])\n",
    "                w.append(1)\n",
    "            else:\n",
    "                e=w[size-1]\n",
    "                if type(e)==int and w[size-2]==S[index]:\n",
    "                    w[size-1]+=1\n",
    "                else:\n",
    "                    w.append(S[index])\n",
    "                    w.append(1)\n",
    "            index+=1\n",
    "        new_str=''.join(map(str,w))\n",
    "        return S if len(new_str)>=len(S) else new_str\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if S == '':\n",
    "            return S\n",
    "\n",
    "        res = ['_', '_']\n",
    "        res_str = ''\n",
    "        for ch in S:\n",
    "            if ch == res[-2]:\n",
    "                res[-1] += 1\n",
    "            else:\n",
    "                res.append(ch)\n",
    "                res.append(1)\n",
    "        res = ''.join([str(x) for x in res])\n",
    "        res = res[2:]\n",
    "        if len(res) >= len(S):\n",
    "            res = S\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        i, j, ls = 0, 0, len(S)\n",
    "        res = []\n",
    "        while i < ls:\n",
    "            while j < ls and S[i] == S[j]:\n",
    "                j += 1\n",
    "            res.append(S[i])\n",
    "            res.append(str(j - i))\n",
    "            i = j\n",
    "        s = ''.join(i for i in res)\n",
    "        return S if len(s) >= len(S) else s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        x=list(S)\n",
    "        slow,fast=0,0\n",
    "        lie=[]\n",
    "        \n",
    "        cont  =0\n",
    "        # lie.append(x[1]+str(len(x)))\n",
    "        # print(lie)\n",
    "        while fast<len(x): \n",
    "                      \n",
    "            if x[slow]==x[fast]:\n",
    "                \n",
    "                cont+=1\n",
    "                fast+=1\n",
    "                if fast ==len(x):\n",
    "                    lie.append(x[slow]+str(cont)) \n",
    "            else:                 \n",
    "                 lie.append(x[slow]+str(cont))\n",
    "                  \n",
    "                 slow =fast \n",
    "                 cont  =0\n",
    "        print(lie)                   \n",
    "        zf=''.join(lie)\n",
    "\n",
    "        print(x)\n",
    "        print(zf)\n",
    "        if len(zf)<len(S):\n",
    "            return zf\n",
    "        else:\n",
    "            return S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        l=list(S)\n",
    "        l1=[]\n",
    "        n= len(l)\n",
    "        num=1\n",
    "        i=0\n",
    "        s1=''\n",
    "        if S=='':\n",
    "           return ''\n",
    "        for i in range(n-1):\n",
    "            if l[i]==l[i+1]:\n",
    "                num+=1\n",
    "            else:\n",
    "                s1=str(l[i])+str(num)\n",
    "                num=1\n",
    "                l1.append(s1)\n",
    "        s1=str(l[-1])+str(num)\n",
    "        l1.append(s1)\n",
    "        print(l1)\n",
    "        if len(l)<=2*len(l1):\n",
    "            return S\n",
    "        else:\n",
    "            return ''.join(l1)\n",
    "\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if len(S) > 50000:\n",
    "            return \n",
    "\n",
    "        arr = ['%s%d' % (a, len(list(b))) for a, b in groupby(S)]\n",
    "        output = ''.join(arr)\n",
    "        return output if len(output) < len(S) else S\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        res = []\n",
    "        S = S + '0'\n",
    "        count = 1\n",
    "        for i in range(1, len(S)):\n",
    "            if S[i] != S[i-1]:\n",
    "                res.append(S[i-1])\n",
    "                res.append(count)\n",
    "                count = 1\n",
    "            else:\n",
    "                count += 1\n",
    "        res = [str(i) for i in res]\n",
    "        res = ''.join(res)\n",
    "        if len(res) < len(S) - 1:\n",
    "            return res\n",
    "        else:\n",
    "            return S[:-1]\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def compressString(self, S: str) -> str:\n",
    "#         if S == '':return S\n",
    "#         res = ''\n",
    "#         pre , count = S[0] , 1\n",
    "#         for c in S[1:]:\n",
    "#             if c == pre:\n",
    "#                 count += 1\n",
    "#             else:\n",
    "#                 res += (pre + str(count))\n",
    "#                 pre , count = c , 1\n",
    "#         res += (pre + str(count))\n",
    "#         return res if len(res) < len(S) else S\n",
    "\n",
    "# 作者：xiao-zhu-ssp\n",
    "# 链接：https://leetcode.cn/problems/compress-string-lcci/solution/mian-shi-ti-06ya-suo-zi-fu-chuan-by-xiao-6ku9/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        lens = len(S)\n",
    "        l = r = cnt = 0\n",
    "        numlist = []\n",
    "        while r < lens:\n",
    "            if S[r] == S[l]:\n",
    "                cnt += 1\n",
    "                r += 1\n",
    "            else:\n",
    "                numlist.append((S[l], cnt))\n",
    "                l = r\n",
    "                cnt = 0\n",
    "        if cnt:\n",
    "            numlist.append((S[l], cnt))\n",
    "        s2 = ''\n",
    "        for char, repnum in numlist:\n",
    "            s2 += char + str(repnum)\n",
    "        return s2 if len(s2) < lens else S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        return min( S, \"\".join(k + str(len(list(v))) for k, v in itertools.groupby(S)), key=len)\n",
    "\n",
    "# 作者：powcai\n",
    "# 链接：https://leetcode.cn/problems/compress-string-lcci/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        return min(S,''.join(k+str(len(list(v))) for k,v in itertools.groupby(S)),key=len)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        \n",
    "       i,j,ls=0,0,len(S)\n",
    "\n",
    "       res=[]\n",
    "\n",
    "       while i<ls:\n",
    "            while j<ls and S[i]==S[j]:\n",
    "               j+=1\n",
    "            res.append(S[i])\n",
    "            res.append(str(j-i))\n",
    "            i=j\n",
    "       res=''.join(res)\n",
    "       return res if len(res)<ls else S\n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self,S:str)->str:\n",
    "        s=\"\".join(a+str(len(list(b))) for a,b in groupby(S))\n",
    "        return s if len(s)<len(S) else S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self,S:str)->str:\n",
    "        s=\"\".join(a+str(len(list(b))) for a,b in groupby(S))\n",
    "        return s if len(s)<len(S) else S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        i, j, n = 0, 0, len(S)\n",
    "        res = []\n",
    "        while i < n:\n",
    "            res.append(S[i])\n",
    "            while j < n and S[i] == S[j]:\n",
    "                j += 1\n",
    "            # res.append(S[i])\n",
    "            res.append(str(j-i)) #注意得将数字转换成字符串\n",
    "            i = j\n",
    "        return ''.join(res) if len(res) < n else S\n",
    "\n",
    "\n",
    "# 双指针法：令 i 指向字符串的「首个字符」， j向前遍历，直到访问到「不同字符」时停止，此时 j−i 便是「首个字符」的连续出现次数，即可完成首个字符的压缩操作。\n",
    "# 接下来，从下个字符开始，重复以上操作，直到遍历完成即可。\n",
    "# 根据题目要求，最终返回「原字符串」和「压缩字符串」中长度较短的那个。\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        tmp=[]\n",
    "        pre=''\n",
    "        cnt=1\n",
    "        for x in S:\n",
    "            if x==pre:\n",
    "                cnt+=1\n",
    "            elif pre!='':\n",
    "                tmp.append(pre+str(cnt))\n",
    "                cnt=1\n",
    "            pre=x\n",
    "        tmp.append(pre+str(cnt))\n",
    "        res=''.join(tmp)\n",
    "        return res if len(res)<len(S) else S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        if len(S) == 0:\n",
    "            return \"\"\n",
    "        pre = S[0]\n",
    "        cnt = 0\n",
    "        vec = []\n",
    "        for ch in S:\n",
    "            if ch == pre:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                vec.append(pre + str(cnt))\n",
    "                pre = ch\n",
    "                cnt = 1\n",
    "        vec.append(pre + str(cnt))\n",
    "        res = \"\".join(vec)\n",
    "        return res if len(res) < len(S) else S\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        i,j,ls = 0,0,len(S)\n",
    "\n",
    "        res = []\n",
    "\n",
    "        while i<ls:\n",
    "            while j <ls and S[i] == S[j]:\n",
    "                j += 1\n",
    "\n",
    "            res.append(S[i])\n",
    "            res.append(str(j-i))\n",
    "            i  =  j\n",
    "\n",
    "        res = ''.join(res)\n",
    "        return res if ls > len(res) else S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def compressString(self, S: str) -> str:\n",
    "#         st = list(S)\n",
    "#         i = 0\n",
    "#         j = 0\n",
    "#         n = len(S)\n",
    "#         res = []\n",
    "#         while i < n:\n",
    "#             count = 0\n",
    "#             while j < n and st[j] == st[i]:\n",
    "#                 j += 1\n",
    "#                 count += 1\n",
    "#             res.append(st[i])\n",
    "#             res.append(count)\n",
    "#             i = j\n",
    "#         res=''.join(map(str,res))\n",
    "#         if len(res)<len(S):\n",
    "#             return res\n",
    "#         else:\n",
    "#             return S\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        n=len(S)\n",
    "        # count=0\n",
    "        i,j=0,0\n",
    "        res=[]\n",
    "        while i<n:\n",
    "            count=0\n",
    "            while j<n and S[j]==S[i]:\n",
    "                j+=1\n",
    "                count+=1\n",
    "            res.append(S[i])\n",
    "            res.append(str(count))\n",
    "            i=j\n",
    "        # return res\n",
    "        res=''.join(res)\n",
    "        if len(res)<len(S):\n",
    "            return res\n",
    "        else:\n",
    "            return S\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(Self, S: str) -> str:\n",
    "        compressed = []\n",
    "        i = 0\n",
    "        while i < len(S):\n",
    "            char = S[i]\n",
    "            count = 1\n",
    "            while i + 1 < len(S) and S[i + 1] == S[i]:\n",
    "                count += 1\n",
    "                i += 1\n",
    "            compressed.append(char)\n",
    "            compressed.append(str(count))\n",
    "            i += 1\n",
    "        return ''.join(compressed) if len(''.join(compressed)) < len(S) else S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        # 双指针\n",
    "        left, right, length = 0, 0, len(S)\n",
    "        res = []\n",
    "        while right < length:\n",
    "            while right < length and S[left] == S[right]:\n",
    "                right += 1\n",
    "            res.append(S[left])\n",
    "            res.append(str(right - left))\n",
    "            left = right\n",
    "        res_str = ''.join(res)\n",
    "        return res_str if len(res_str) < length else S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        \n",
    "        if not S: return S\n",
    "        n =len(S)\n",
    "\n",
    "        queue = []\n",
    "        queue.append(S[0])\n",
    "        count = 1\n",
    "        i = 1\n",
    "        while i < n:\n",
    "            if S[i] == S[i-1]:\n",
    "                count += 1\n",
    "            else:\n",
    "                queue.append(str(count))\n",
    "                queue.append(S[i])\n",
    "                count = 1\n",
    "            i += 1\n",
    "\n",
    "        queue.append(str(count))\n",
    "        if len(queue) < len(S):\n",
    "            return ''.join(queue)\n",
    "        else :\n",
    "            return S\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def compressString(self, S: str) -> str:\n",
    "        Length = len(S)\n",
    "        if Length <= 2:\n",
    "            return S\n",
    "\n",
    "        i = 0\n",
    "        j = 0\n",
    "        count = 0\n",
    "        result = []\n",
    "        while j < Length:\n",
    "            if S[i] != S[j]:\n",
    "                result.append(S[i])\n",
    "                result.append(str(count))\n",
    "                count = 0\n",
    "                i = j\n",
    "            else:\n",
    "                j += 1\n",
    "                count += 1\n",
    "        \n",
    "        if count:\n",
    "            result.append(S[i])\n",
    "            result.append(str(count))\n",
    "        \n",
    "        return ''.join(result) if len(result) < Length else S\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
